﻿/*
输入：
7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9
输出：
12
*/
// N个车站，M条路
string[] NMStr = Console.ReadLine().Split(" ");
int N = int.Parse(NMStr[0]);
int M = int.Parse(NMStr[1]);

// 构建图 -- 邻接表
List<(int ,int)>[] graph = new List<(int, int)>[N+1];
for (int i = 0; i < N+1; i++)
{
    graph[i] = new List<(int, int)>();
}

for (int i = 0; i < M; i++)
{
    string[] stvStr = Console.ReadLine().Split(" ");
    int s = int.Parse(stvStr[0]);
    int t = int.Parse(stvStr[1]);
    int v = int.Parse(stvStr[2]);
    graph[s].Add((t, v));
}

// 单源最短路径问题
bool[] visited = new bool[N + 1]; // 访问数组
int[] minDist = new int[N + 1]; // 各点到集合的最短距离
Array.Fill(minDist, int.MaxValue);
minDist[1] = 0;
for (int i = 1; i <= N; i++)
{
    // 1、获取最近点 -- 未访问
    int index = 0;
    int min = int.MaxValue;
    for (int j = 1; j < minDist.Length; j++)
    {
        if(visited[j]) continue;
        if (min > minDist[j])
        {
            min = minDist[j];
            index = j;
        }
    }
    
    // 2、访问
    visited[index] = true;
    
    // 3、更新距离
    for (int j = 0; j < graph[index].Count; j++)
    {
        (int t, int v) = graph[index][j];
        minDist[t] = minDist[t] > minDist[index] + v ? minDist[index] + v : minDist[t];
    }
}

Console.WriteLine(minDist[N] == int.MaxValue ? -1 : minDist[N]);
